package dq.utils;

import java.util.HashMap;
import java.util.Map;

/**
 * @author DQ
 * @version 1.0
 * @date 2021/1/7 17:30
 */

public class SlidingWindow {

    public static String minWindows(String s, String t){

        Map<Character, Integer> windows = new HashMap<Character, Integer>();
        Map<Character, Integer> need = new HashMap<Character, Integer>();
        // windows与need中同key同value的数量
        int valid = 0;
        int start = 0;
        int len=s.length();
        int left = 0;
        int right = 0;
        //遍历原始字符串，初始化need
        for (Character c : t.toCharArray()){
            if(!need.containsKey(c)){
                need.put(c,0);
            }
            need.put(c, need.get(c)+1);
        }


        while(right<s.length()){

            // c是进入窗口的字符
            char c = s.charAt(right);
            // 滑动窗口，保持左闭右开的区间[left, right)
            right++;
            //入股当前字符是need需要的字符
            if(need.containsKey(c)){
                if (!windows.containsKey(c)){
                    windows.put(c,0);
                }
                windows.put(c,windows.get(c)+1);

                if (windows.get(c) == need.get(c)){
                    valid++;
                }
            }
            //判断左侧窗口是否要收缩
            while(valid==need.size()){
                if(right-left<len){
                    start = left;
                    len = right - left;
                }
                //d是滑出窗口的字符
                char d = s.charAt(left);
                left++;
                if (need.containsKey(d)){
                    //如果说 windows存的和需要的相同，则将有效值减去一
                    //windwos在向右滑动时会添加可能会天剑多个相同的
                    //比如 S="BBCDA",T="ABC"，在向右滑动时，添加了两个B
                    // 如果不做判断直接将valid-1的话，会出错，因为即便取出一个B，也满足条件
                    if(windows.get(d)==need.get(d)){
                        valid--;
                    }
                    windows.put(d, windows.get(d)-1);
                }
            }
        }
        return s.substring(start,start+len);
    }

    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        System.out.println(minWindows(s,t));
    }
}
